package com.LeeCode;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * 叶子相似的树
 */

public class Code872 {
    public static void main(String[] args) {
        Integer[] arr1 = {3, 5, 1, 6, 2, 9, 8, null, null, 7, 4};
        Integer[] arr2 = {3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8};
        TreeNode root1 = Utils.buildTree(arr1);
        TreeNode root2 = Utils.buildTree(arr2);
        System.out.println(new Code872().leafSimilar(root1, root2));

    }

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        postOrder(root1, list1);
        postOrder(root2, list2);

        return list1.equals(list2);
    }

    private void postOrder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        postOrder(root.left, list);
        postOrder(root.right, list);
        if (root.left == null && root.right == null) { // 添加叶子节点序列
            list.add(root.val);
        }
    }
}
